home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / strlib.zip / _STR2PAT.C < prev    next >
Text File  |  1993-01-04  |  2KB  |  44 lines
  1.  
  2. /*  File   : _str2pat.c
  3.     Author : Richard A. O'Keefe.
  4.     Updated: 2 June 1984
  5.     Defines: _pat_lim, _pat_vec[], _str2pat()
  6.  
  7.     Searching in this package is done by an algorithm due  to  R.  Nigel
  8.     Hospool,  described  in  Software  Practice & Experience 1980, p505.
  9.     Elsewhere I have a version of it which does  exact  case  or  either
  10.     case  match,  word  more or literal mode, forwards or backwards, and
  11.     will look for the Nth instance.  For most applications that  is  too
  12.     much  and  a  simple  exact  case forward search will do.  Hospool's
  13.     algorithm is a simplification of  the  Boyer-Moore  algorithm  which
  14.     doesn't  guarantee linear time, but in practice is very good indeed.
  15.  
  16.     _str2pat(pat) builds a search table for the string pat.  As usual in
  17.     this pacakge, if pat == NullS, the table is not changed and the last
  18.     search string is re-used.  To support  this,  _str2pat  returns  the
  19.     actual search string.
  20. */
  21.  
  22. #include "strings.h"
  23. #include "_str2pat.h"
  24.  
  25. int     _pat_lim;
  26. int     _pat_vec[_AlphabetSize];
  27. static  _char_  *oldPat = "";
  28.  
  29.  
  30. _char_ *_str2pat(pat)
  31.     register _char_ *pat;
  32.     {
  33.         register int L, i;
  34.  
  35.         if (pat == NullS) pat = oldPat; else oldPat = pat;
  36.         for (L = 0; *pat++; L++) ;
  37.         for (i = _AlphabetSize; --i >= 0; _pat_vec[i] = L) ;
  38.         for (pat = oldPat, i = L; --i > 0; _pat_vec[*pat++] = i) ;
  39.         _pat_lim = --L;
  40.         return oldPat;
  41.     }
  42.  
  43.  
  44.